package stack_queue.queue.impl;

import stack_queue.queue.IQueue;

import java.util.NoSuchElementException;

/**
 * 基于链表实现的基础队列
 * @param <E>
 */
public class MyQueue<E> implements IQueue<E> {
    // 链表的每个节点
    private class Node{
        E val;
        Node next;

        public Node(E val){
            this.val=val;
        }
    }

    // 当前队列中的元素个数
    private int size;
    // 队首
    private Node head;
    //队尾
    private Node tail;

    @Override
    public void offer(E val) {
        Node node=new Node(val);
        if(head==null){
            // 此时链表为空
            head=tail=node;
        }else {
            tail.next=node;
            tail=node;
        }
        size++;
    }

    @Override
    public E poll() {
        if(isEmpty()){
            throw new NoSuchElementException("queue is empty! cannot poll");
        }
        Node node=head;
        head=node.next;
        // 将原来头节点脱钩
        node.next=null;
        size--;
        return node.val;
    }

    @Override
    public E peek() {
        if(isEmpty()){
            throw new NoSuchElementException("queue is empty! cannot peek");
        }
        return head.val;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        sb.append("[");
        // 链表的遍历
        for(Node x=head;x!=null;x=x.next){
            sb.append(x.val);
            if(x.next!=null){
                // 还没走到链表尾部
                sb.append(",");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}
